package test.n00100;


import java.util.Arrays;

public class Problem00191 {
    public static void main(String[] args) {
        println(new int[]{1, 2, 3, 4, 5}, 2);
        println(new int[]{1, 2}, 1);
        println(new int[]{1, 2}, 2);
        println(new int[]{1}, 1);
    }

    public static void println(int[] nums, int n) {
        Solution ss = new Solution();
        System.out.println(Arrays.asList(nums) + "," + (nums.length - n) + "," + ss.removeNthFromEnd(create(nums), n));
    }

    public static ListNode create(int[] a1) {
        ListNode[] list = new ListNode[a1.length];
        for (int i = 0; i < a1.length; i++) {
            list[i] = new ListNode(a1[i]);
            if (i > 0) {
                list[i - 1].next = list[i];
            }
        }

        return list[0];
    }

    public static class Solution {

        /**
         * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
         *
         * 解题思路:
         * 找到前一个节点，然后执行删除操作
         *
         * @param head
         * @param n
         * @return
         */
        public ListNode removeNthFromEnd(ListNode head, int n) {
            int len = 0;
            ListNode t = head;
            while (t != null) {
                len++;
                t = t.next;
            }

            // 链表前面加一个节点
            ListNode dummy = new ListNode(0, head);

            int before = len - n;
            ListNode cur = dummy;
            while(before > 0) {
                before--;
                cur = cur.next;
            }
            cur.next = cur.next.next;
            return dummy.next;
        }
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
